package tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 257. 二叉树的所有路径
 * 给定一个二叉树，按 任意顺序 ,返回所有从根节点到叶子节点的路径。
 * <p>
 * 说明: 叶子节点是指没有子节点的节点。
 */
public class BinaryTreePaths_257 {
    StringBuilder path = new StringBuilder();

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        path.append(root.val);
        getPath(res, root);
        return res;
    }

    private void getPath(List<String> paths, TreeNode root) {
        if (root.left == null && root.right == null) {
            paths.add(path.toString());
            return;
        }

        // 不能把root的值删除了，所以要记录len
        int len = path.length();
        if (root.left != null) {
            path.append("->");
            path.append(root.left.val);
            getPath(paths, root.left);
            // 删除新添加上去的的路径，只保留根路径
            path.delete(len, path.length());
        }

        if (root.right != null) {
            path.append("->");
            path.append(root.right.val);
            getPath(paths, root.right);
            // 删除新添加上去的的路径，只保留根路径
            path.delete(len, path.length());
        }
    }
}
